\chapter{基础算法}
\section{排序算法}
\begin{definition}[稳定性]
	如果a原本在b的前面且a=b排序后a仍然在b的前面，则成为稳定排序,否则称为不稳定排序。
\end{definition}
\begin{table}[!htbp]
	\begin{tabular}{lllllll}
		\toprule
		排序算法    & 时间复杂度          & 最好情况           & 最坏情况           & 空间复杂度     & 排序方式 & 是否为稳定排序 \\
		\midrule
		冒泡排序    & $O(n^2)$       & $O(n)$         & $O(n^2)$       & $O(1)$    & 原地   & 是       \\
		选择排序    & $O(n^2)$       & $O(n^2)$       & $O(n^2)$       & $O(1)$    & 原地   & 否       \\
		插入排序    & $O(n^2)$       & $O(n)$         & $O(n^2)$       & $O(1)$    & 原地   & 是       \\
		shell排序 & $O(nlogn)$     & $O(nlogn)$     & $O(nlong)$     & $O(1)$    & 原地   & 否       \\
		归并排序    & $O(nlogn)$     & $O(nlogn)$     & $O(nlogn)$     & $O(n)$    & 非原地  & 是       \\
		快速排序    & $O(nlogn)$     & $O(nlogn)$     & $O(n^2)$       & $O(logn)$ & 原地   & 否       \\
		堆排序     & $O(nlogn)$     & $O(nlogn)$     & $O(nlogn)$     & $O(1)$    & 原地   & 否       \\
		计数排序    & $O(n+k)$       & $O(n+k)$       & $O(n+k)$       & $O(k)$    & 非原地  & 是       \\
		桶排序     & $O(n+k)$       & $O(n+k)$       & $O(n^2)$       & $O(n+k)$  & 非原地  & 是       \\
		基数排序    & $O(n\times k)$ & $O(n\times k)$ & $O(n\times k)$ & $O(n+k)$  & 非原地  & 是       \\
		\bottomrule
	\end{tabular}
	\caption{排序算法性能}
\end{table}
\subsection{选择排序}
将待排序的数组中最小元素和数组中第一个元素交换（如果最小的元素就是第一个元素就自己和自己交换），然后依次在剩余的数组中找到最小的元素将其和待排序的数组中第二个元素交换，一直到结束。
\begin{itemize}
	\item 时间复杂度：$O(n^2)$
	\item 空间复杂度：$O(1)$
	\item 非稳定排序
	\item 原地排序
\end{itemize}
\begin{longlisting}
	\caption{选择排序}
	\cppfile[firstline=194,lastline=212]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:chooseSort}
\end{longlisting}

\subsection{快速排序}
\begin{algorithm}[!htbp]
	\caption{快速排序}
	\label{al:al2}
	\begin{algorithmic}
		\STATE 数组长度为n，索引下标为1
		\WHILE{数组不是全局有序}
		\STATE 选择轴值，将序列划分乘两个子序列L和R，使得L中所有记录小于或者等于轴值，R中记录都大于轴值。
		\IF{如果数组全局有序}
		\STATE 排序结束
		\ELSE
		\STATE 对子序列分别排序。
		\ENDIF
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}
关于分区方法，通常有两种算法：
\begin{itemize}
	\item Hoare 分区方案：
	\item Lomuto 分区方案：
\end{itemize}
轴值的选择，尽可能使L和R长度相等。选择的方案：选择最左边的记录，随机选择和选择平均值。快速排序的算法框架:
\begin{longlisting}
	\caption{快排算法框架}
	\cppfile[firstline=74,lastline=80]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:QuickSort}
\end{longlisting}
分割函数：
\begin{longlisting}
	\caption{快排Partition 操作}
	\cppfile[firstline=59,lastline=73]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:Partition}
\end{longlisting}
\begin{enumerate}
	\item 数组范围内生成一个随机索引，将其值作为轴值和末尾的元素交换。
	\item 左边的begin指针右移找到第一个小于轴值的元素，然后和最左边的元素交换，指向最左边的索引+1。
	\item 左指针到达右指针结束，将步骤一的轴值和指向最左边的位置交换。此时轴值左边的元素均小于它，右边均大于它。
\end{enumerate}
操作示意图如\figref{fig:randomPartion}。
\begin{figure}
	\begin{center}
		\includegraphics[width=0.95\textwidth]{randomPartion}
	\end{center}
	\caption{随机Partion操作示意图}
	\label{fig:randomPartion}
\end{figure}
关于 Partition 操作，有不同的实现，这里先描述一下《数据结构与算法》里面的实现，这里数组左右开始位置分别是left、right。l和r分别表示左右移动的指针，这里privot选择right位置。
\begin{itemize}
	\item l初始位置为left-1的位置。对于r从left到right-1的位置分别进行如下操作：
	      \begin{enumerate}
		      \item 如果 r 当前元素$\geq num[privot]$，l+1，交换num[l+1]和num[r]的位置，否则r右移直到r-1为止位置。
		      \item 循环结束后将l+1的位置和r（privot）位置的元素交换。
	      \end{enumerate}
\end{itemize}

\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.95\textwidth]{partition1}
	\end{center}
	\caption{partition操作示意图}
	\label{fig:partition}
\end{figure}
如图\figref{fig:partition}：
\begin{itemize}
	\item r从0开始出发到right-1的位置，发现0位置所在元素小于nums[privot]
\end{itemize}
时间代价，长度为n的序列，时间为T(n),选择轴的时间为常数，分割时间为cn,分割后长度分别为i和n-i-1。左右子序列T(i)和T(n-i-1)，递推方程$T(n) = T(i)+T(n-i-1)+cb$,总时间代价为:$T(n)=T(1)+c\sum_{i=2}^ni=\Theta(n^2)$。最佳情况下$T(n)=2T(n/2)+cn=cnlogn+n=\Theta(nlogn)$，等概率情况下，轴值数组分成长度为0和n-1,1和n-2,子序列的概率相等，都为1/n。$T(n)=\Theta(nlogn)$
\begin{example}[一种版本的快排实现]
	将待排序的数组左边的第一个元素作为privot，使用索引i从左到右、j从右到左，分别找到大于基准、小于基准的两个数，交换其值直到i=j,这时候的这个位置为基准应该待的位置，于是将基准值和这个值交换。一遍排序完成。接下来递归的排序，left到i-1和i+1到right。反复直到left<=right。排序过程如\figref{fig:fastsort_process}：
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{fastsort_process}
	\caption{快速排序过程}
	\label{fig:fastsort_process}
\end{figure}

\begin{longlisting}
	\caption{常规快速排序}
	\cppfile[firstline=56,lastline=80]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:fastsort}
\end{longlisting}

\subsection{插入排序}
插入排序：将每一张牌插入已排序的数组中的适当位置，排序过程如下：
\begin{enumerate}
	\item 从数组中第二个元素开始抽取元素。
	\item 把它和左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去直到遇到比它小的元素放在该元素的后面。
	\item 反复执行步骤2，直到结束。
\end{enumerate}
\begin{itemize}
	\item 时间复杂度：$O(n^2)$
	\item 空间复杂度：$O(1)$
	\item 稳定排序
	\item 原地排序
\end{itemize}
\begin{algorithm}
	\caption{插入排序算法}
	\label{al:al2}
	\begin{algorithmic}
		\STATE 数组长度为n，索引下标为1
		\WHILE{下标不等于n-1}
		\STATE 比较索引所在元素和之前的元素
		\IF{大于前一个元素。}
		\STATE 则该元素放在前一个元素后面，索引+1。
		\ELSIF{大于某一个元素小于另一个元素。}
		\STATE 插入到两个数之间，索引+1。
		\ELSE
		\STATE 插入到第一个元素之前，索引+1。
		\ENDIF
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{insert_sort}
	\caption{插入排序算法过程}
\end{figure}
\textbf{代码实现：}
TODO： 插入排序纳入排序算法组里面
%\begin{longlisting}
%	\caption{插入排序}
%	\cppfile[firstline=3,lastline=17]{code/arith/sort/main.cpp}
%	\label{code:insertSort}
%\end{longlisting}

\begin{itemize}
	\item 该算法稳定。
	\item 空间代价$\Theta$（因为分配空间存储临时的值temp用来交换)
	\item 时间代价：
	      \begin{itemize}
		      \item 最佳情况：n-1此比较，2(n-1)（每个元素线移动到临时变量temp，之后移到对应位置）次移动，
		      \item 最差情况：$\Theta(n^2)$
		            \begin{itemize}
			            \item 比较1~n-1个，共$\frac{n(n-1)}{2}=\Theta(n^2)$
			            \item 移动次数：$\sum_{i=1}^{n-1}(i+2)=(n-1)(n+4)/2=\Theta(n^2)$(第i个元素一出一进2此，前面的元素移动i次，总共i+2次)
		            \end{itemize}
		      \item 平均情况$\Theta(n^2)$

	      \end{itemize}
\end{itemize}
插入排序最好情况下时间代价$\Theta(n)$,对于短序列比较有效。
\subsection{冒泡排序}
将待排序数组的第一个元素和后一个元素比较，如果大于后一个元素，则交换两个元素的位置。接着比较第二个元素和第三个元素同样的方式比较到倒数第二个元素。一次比较完成，最大值在最右边。接着执行同样的操作到道速第三个直到第二个元素。
\begin{itemize}
	\item 时间复杂度：$O(n^2)$
	\item 空间复杂度：$O(1)$
	\item 稳定排序
	\item 原地排序
\end{itemize}
\begin{longlisting}
	\caption{冒泡排序}
	\cppfile{third_party/coding/cxx/algorithm/common/src/bublesort.cc}
	\label{code:bubbleSort}
\end{longlisting}

\subsection{Shell排序}
Shell排序是插入排序的变种。无论是插入排序还是冒泡排序，如果数组的最大值就在第一位，要将它挪到正确的位置就需要n-1次移动。也就是说原数组的一个元素如果距离它正确的位置很远的话，则需要相邻元素交换很多次才能达到正确的位置。Shell排序就是为了加快速度改进的插入排序，交换不相邻的元素对数组局部排序。Shell排序的思想史采用插入排序的方法，先让数组中任意间隔为h的元素有序，刚开始h的大小可以使h=n/2接着让h=n/4让h一直缩小，当h=1的时候，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的。
\begin{itemize}
	\item 时间复杂度$O(nlog(n))$
	\item 空间复杂度$O(1)$
	\item 非稳定排序
	\item 原地排序
\end{itemize}
\begin{algorithm}
	\caption{Shell排序算法}
	\label{al:shellSort}
	\begin{algorithmic}
		\WHILE{跨度n/2}
		\IF{跨度!=1}
		\STATE 以跨度为n/2两两交换对应位置的逆序数。
		\ELSE
		\STATE 以跨度为1插入排序后跳出。
		\ENDIF
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{shell_sort}
	\caption{Shell排序过程}
\end{figure}
代码实现\coderef{code:shellSort}。
TODO: shell排序重写
算法分析：
\begin{itemize}
	\item 不稳定
	\item 空间代价$\Theta(1)$
	\item 时间代价
	      \begin{itemize}
		      \item 增量每次除以2,$\Theta(n^2)$
		      \item 选择适当的增量，可以使得时间代价接近$\Theta(n)$
	      \end{itemize}
\end{itemize}
\subsection{堆排序}
\begin{definition}[堆]
	堆是一种树形结构，它的节点比两个子节点都大。数据表示的堆一个节点索引为k,左节点索引为2k,右节点为索引2k+1。知道节点索引k，其父节点索引为k/2。
\end{definition}
堆排序需要：
\begin{itemize}
	\item 构建最大堆。
	\item 将最大堆的根节点和最后一个元素交换，然后构造最大堆。
	\item 将倒数第二个元素和最大堆根节点交换，反复直到结束。
\end{itemize}
最大堆调整过程：
\begin{itemize}
	\item 找到最后一个非叶子节点（索引在n/2-1位置）作为根节点。
	\item 如果这个节点左右子节点中更大的一个更新最大值索引。
	\item 如果最大孩子不等于此节点，则交换根节点和最大节点，然后对当前最大节点递归调用此算法。
\end{itemize}
初始化最大堆如\figref{fig:heap_init}，数组模拟堆，索引为n的节点的左右孩子的索引分别是$n\times2+1$、$n\times2+2$。构建堆操作：\coderef{code:buildHeap}。
\begin{figure}
	\centering
	\includegraphics[width=.7\textwidth]{heap_init}
	\caption{数组视角下的堆结构}
	\label{fig:heap_init}
\end{figure}
\begin{longlisting}
	\caption{最大堆调整（构建完整的最大堆需要对非叶子节点都做调整）}
	\cppfile[firstline=82,lastline=94]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:buildHeap}
\end{longlisting}
最大堆构建过程如\figref{fig:heapBuild}：
\begin{itemize}
	\item 从最大堆的最后一个非叶子节点开始往前遍历，直到整个堆的根，对于每个节点，使用上述调整算法调整。
\end{itemize}
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{heapBuild}
	\caption{最大堆的构建}
	\label{fig:heapBuild}
\end{figure}
堆 \figref{fig:heapBuild} 执行过程解释：
\begin{enumerate}
	\item 通过数组最大索引除以2（4）找到最大索引所在位置。
	\item 对比其左右子孩子找到更大的元素和当前节点交换。这里1比7小，不交换。
	\item 找到下一个非叶子节点3（14）其左右节点均比其小。不交换。
	\item 找到下一个非叶子节点2（10），其左右节点均比其小，不交换。
	\item 找到下一个非叶子节点1（4），其左节点（14）更大，14和其交换，交换后会导致以前已经遍历过的子节点比根节点小的规则破坏则需重新调整。
	\item 根据刚刚调整的节点位置找到对应子节点调整，发现8（8）大于3（4），交换。
	\item 找到最后一个非叶子节点0（16），此时其为最大值。
\end{enumerate}

\begin{longlisting}
	\caption{构建最大堆}
	\cppfile[firstline=21,lastline=26]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:maxHeap}
\end{longlisting}
\begin{longlisting}
	\caption{堆排序}
	\cppfile[firstline=102,lastline=108]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:heapSort}
\end{longlisting}

\begin{longlisting}
	\caption{最大堆AST}
	\cppfile[firstline=1,lastline=113]{third_party/coding/cxx/datastruct/tree/src/MaxHeap.cc}
	\label{code:maxHeapAST}
\end{longlisting}
\subsection{归并排序}
先划分，再归并。
\begin{itemize}
	\item 分解原问题为若干子问题，子问题是原问题的规模较小的示例。
	\item 解决子问题，若干子问题规模足够小则直接求解。
	\item 合并子问题为原问题的解。
\end{itemize}
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{mergesort_process}
	\caption{归并排序}
\end{figure}

\begin{longlisting}
	\caption{归并排序}
	\cppfile[firstline=175,lastline=204]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:mergeSort}
\end{longlisting}
辅助函数Merge(Array,p,q,r)用来将已经排序好的两个子数组Array[p,q]、Array[q+1,r]合并为一个整体。
\subsection{桶排序}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{bucketsort}
	\caption{桶排序}
	\label{fig:bucketsort}
\end{figure}
假设排序数据服从[0-1)的均匀分布。然后对于[0-0.1)、[0.1-0.2)、……，[0.9-1)的10个桶，将属于各自区间的元素放入桶中，放入的时候按照顺序放置。然后遍历整个桶，将里面的元素分别取出拼接为最终数组。排序流程如\figref{fig:bucketsort}
\begin{longlisting}
	\caption{桶排序}
	\cppfile[firstline=214,lastline=236]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:bucketSort}
\end{longlisting}
性能分析：数组长度为n，所有记录区减[0,m),时间代价为：统计桶的数量需要遍历数组代价为$\Theta(n)$,累加桶需要对桶的前m个元素求和，代价为$\Theta(m)$，总的时间代价为$\Theta(n+m)$,空间代价：需要m个计数器（记录元素次数）和长度为n的临时数组（排序存放的数组）。$\Theta(m+n)$。算法稳定。该算法适用于：\textcolor{red}{m相对于n很小的情况。否则桶的统计代价就很大。}
\subsection{计数排序}
对于待排序数组中的元素a，使用[0-max(a)]的中的元素填充的数组c。通过c纪录数组a中每个元素出现的频率，因为存在同一个元素出现两次的情形。对于数组c中的元素再次求以纪录小于index的元素有多少个。然后 b 为排序之后的数组，从后向前遍历数组 a，找到b[a[i]] = a[i]（小于a[i]的元素个数为b[a[i]]，a[i]应该放于此）。这时候 a[i] 已经放到了正确的位置，所以更新 c[a[i]] = c[a[i]]-1。
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{counter_sort}
	\caption{计数排序流程}
	\label{fig:counter_sort}
\end{figure}
这里需要说明的是计算小于n的元素的个数，算法通过统计元素出现的次数，然后累计求和实现 $O(n)$ 完成。
\begin{longlisting}
	\caption{计数排序}
	\cppfile[firstline=238,lastline=258]{third_party/coding/cxx/algorithm/common/src/sortAlgorithm.cc}
	\label{code:countSort}
\end{longlisting}
\section{数组}
\subsection{数组中查找元素}
\begin{example}
	在一个长度为n+1的数组中找到重复的数组，数字范围为1-n。不允许修改原始的数组。
\end{example}
\begin{Mind}{数组中查找元素}{}
	类似二分法查找的思想，如果数组数值范围为1-n,但是数组长度为n+1,说明肯定有重复数字。也就是说可以通过数值范围和数组长度判断重复数字出现的区域。
\end{Mind}
假如数组为[2,3,5,4,3,2,6,7]有8（n+1）个元素。数值范围在1-7(n)之间。
	如果在1-4之间数组中的元素个数大于4，那么重复数字的范围在1-4之间，统计1-4之间出现的数的个数为5，所以重复数字在1-4之间。在1-2之间出现的元素有2,3-4出现的元素有3个。重复元素出现在3-4之间。接着对3-4之间的元素分别统计获取3出现两次，4出现一次。
	时间复杂度为：$O(nlogn)$空间复杂度为$O(1)$。实现\coderef{code:getDuplication}。
\begin{longlisting}
	\caption{数组中查找元素}
	\cppfile[firstline=4,lastline=49]{third_party/coding/cxx/algorithm/common/src/getDuplication.cc}
	\label{code:getDuplication}
\end{longlisting}
\begin{remark}
	该代码存在的问题是能找到重复的数，但是不能找到所有的重复的数（比如2）。
\end{remark}
\subsection{旋转矩阵}
给定一个 $n\times n$ 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。操作示意图如\figref{fig:rotate}：
\begin{figure}
	\begin{center}
		\includegraphics[width=0.5\textwidth]{rotate}
	\end{center}
	\caption{旋转图像}
	\label{fig:rotate}
\end{figure}
\begin{Mind}{旋转图像}
	水平方向翻转，然后沿着主对角线翻转。
\end{Mind}
实现示意图如\figref{fig:rotate_op}。
\begin{figure}
	\begin{center}
		\includegraphics[width=0.5\textwidth]{rotate_op}
	\end{center}
	\caption{图像原地旋转示意图}
	\label{fig:rotate_op}
\end{figure}
需要注意的是水平方向上翻转需要考虑是奇数行还是偶数行，比如5行，翻转索引是0,1，4行翻转索引也是0,1。实现如\coderef{code:rotate}。
\begin{longlisting}
	\caption{旋转图像}
	\cppfile[firstline=33,lastline=46]{third_party/coding/cxx/algorithm/common/src/rotate.cc}
	\label{code:rotate}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度$O(n^2)$。
	\item 空间复杂度$O(1)$。
\end{itemize}
\subsection{矩阵置0}
算法实现：
\begin{enumerate}
	\item 扫描矩阵首行首列，如果发现有0说明此行列需要被置0，使用行列标记存储。
	\item 对非首行首列的位置，发现0，则将0的信息存储到首行首列。
	\item 扫描首行首列将对应行列置0。
	\item 根据首行首列标记对首行或者首列置0。
\end{enumerate}
算法实现如\coderef{code:setZeros}。相比于直接记录0所在的位置的实现，此做法操作复杂了一些，但是空间复杂度为O(1)。
\begin{longlisting}
	\caption{矩阵置0}
	\cppfile[firstline=25,lastline=79]{third_party/coding/cxx/algorithm/common/src/setZeroes.cc}
	\label{code:setZeros}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(mn)。
	\item 空间复杂度O(1)。
\end{itemize}
\subsection{螺旋矩阵}
\begin{example}[螺旋矩阵]
给定一个$m \times n$大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
\begin{Textcode}
	示例1
	输入
	[[1,2,3],[4,5,6],[7,8,9]]
	返回值
	[1,2,3,6,9,8,7,4,5]
\end{Textcode}
\end{example}

\begin{Mind}{螺旋矩阵}
	用上下左右四个标记，遍历最外围一行后top+1,遍历最外围右侧列后right-1，遍历最外围底部后bottom+1，遍历最外围左边后，left++。如果left>right或者bottom>top则循环结束。
\end{Mind}
\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{spiral}
	\label{fig:spiral}
	\caption{螺旋矩阵示意图}
\end{figure}
对于11、12两个元素，按照同样的算法，先获取左上角的一段长度为(cols-1=1)的元素，然后获取右上角到rows-1=0的元素，这时值为0，计算值漏了。所以需要将此值补上。
\begin{longlisting}
	\caption{螺旋矩阵}
	\cppfile[firstline=7,lastline=41]{third_party/coding/cxx/algorithm/common/src/spiralOrder.cc}
	\label{code:spiralOrder}
\end{longlisting}
\subsection{在二维数组中查找指定的数}
\begin{example}[在二维数组中查找指定的数]
在二维数组中查找指定的数
\begin{gather*}
	\begin{bmatrix}
		1 & 2 & 8  & 9  \\
		2 & 4 & 9  & 12 \\
		4 & 7 & 10 & 13 \\
		6 & 8 & 11 & 15 \\
	\end{bmatrix}
\end{gather*}
\end{example}
\begin{Mind}{在二维数组中查找指定的数}{}
在二维数组中，因为每一行都是从左向右递增，从上到下递增。从数组右上角开始，如果右上角数字大于当前数字，则此数字所在列都不用查找（必然大于目标value）于是到倒数第二列，一直找到第一列，如果等于目标value则直接返回，如果小于则对该列从上往下找，如果数字小于目标value则这一行都不需要考虑（目标左边都比value小），只能向下找，如果找到比value大，则不需查找（下面的值都比value大），找到等于的就返回。
\end{Mind}
\begin{longlisting}
	\caption{二维数组中查找特定的数}
	\cppfile[firstline=5,lastline=24]{third_party/coding/cxx/algorithm/common/src/findNumberIn2DArray.cc}
	\label{code:productExceptSelf}
\end{longlisting}

\subsection{除自身外数组的乘积}
\begin{example}[除自身外数组的乘积]
给你一个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。题目数据保证 数组nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
\begin{Textcode}
	输入: nums = [1,2,3,4]
	输出: [24,12,8,6]
\end{Textcode}
\end{example}
\begin{Mind}{除自身外数组的乘积}{}
	对于数组中每个元素，找到其左边元素的乘积和右边元素的乘积然后对应相乘即可。例如1左边没有元素乘积初始化为1，右边元素2、3、4，乘积24，则除去1之后的乘积为24，对于2，左边元素的乘积为1，右边元素3、4的乘积为12，结果为12，以此类推。
\end{Mind}
算法示意图如：\figref{fig:productExceptSelf}。
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.6\textwidth]{productExceptSelf}
	\end{center}
	\caption{通过左右乘积计算}
	\label{fig:productExceptSelf}
\end{figure}

\begin{longlisting}
	\caption{除自身外数组的乘积}
	\cppfile[firstline=3,lastline=19]{third_party/coding/cxx/algorithm/common/src/productExceptSelf.cc}
	\label{code:productExceptSelf}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(n)。
\end{itemize}
上述\coderef{code:productExceptSelf}实现中我们分别计算左边和右边的乘积和最后在一起求和，这部分可以合并在一起降低空间复杂度。因为输出不计入到空间复杂度计算，所以先用输出计算左乘积。然后更新输出的时候从末尾元素开始这样避免覆盖输出中的元素。

\begin{longlisting}
	\caption{除自身外数组的乘积}
	\cppfile[firstline=21,lastline=38]{third_party/coding/cxx/algorithm/common/src/productExceptSelf.cc}
	\label{code:productExceptSelfOpt}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度O(n)。
	\item 空间复杂度O(1)。
\end{itemize}
% \subsection{H 指数}
% 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

\subsection{寻找数组中乘积最大结果}
\begin{example}{在无序数组中找到三个数使得乘积最大，数组中包含有正数和负数。}
\end{example}
\begin{Mind}{数组乘积最大}{}
	无序数组中既然包含正数说明正数个数至少有一个，最大数为正数。同理最小数为负数。这时候分为如下几种情况(为了方便说明，这里假设有第二大，第三大，最小，次小)：
	\begin{itemize}
		\item 如果第一个小于0的数是第二大的数，这时候第二大的数和第三大的数均为负数，判断三个数的乘积最大变成了第二大和第三大的数的乘积和最小数和次小数乘积谁更大。
		\item 如果第一个小于0的数是第三大的数，乘积最大肯定是$\text{最大数}\cdot\text{最小数}\cdot{次小数}$，因为它两都为负数乘积为正数。
		\item 如果第一个小于0的数是次小数，这时候和情况1相同，第二大数和第三大数都是正数，最小数和次小数都是负数，它两的乘积为正数。所以最大数需要判断最小数和次小数的乘积和第二大与第三大数的乘积谁更大。
		\item 如果第一个小于0的数是最小数，这时候最大乘积肯定是$\text{最大数}\cdot\text{第二大}\cdots\text{第三大}$
	\end{itemize}
\end{Mind}
综上所述，实际上只要比较最大值和第二大，第三大的值乘积和最大值和最小值，次小值的乘积选出最大的乘积即可。一次扫描数组时间代价O(n),空间代价存储第二大，第三大数的乘积和最小数和次小数的乘积即可。空间代价O(1)。
代码如下：
TODO: 寻找数据中乘积最大的结果，需要重构
%\begin{longlisting}
%	\caption{数组乘积最大}
%	\cppfile[firstline=1,lastline=35]{code/arith/ex90/main.cpp}
%	\label{code:数组乘积最大}
%\end{longlisting}
\subsection{蚂蚁过河问题}
\begin{example}
	在一根长为L的水平木棍上有一群数量为n的蚂蚁，它们以每秒1cm/s的速度走到木棍一端就会掉下去。现在知道它们的起始位置是距离木根左端点的x处。但是不知道它们爬行的方向。在相向而行的两只蚂蚁相遇后，它们会掉头往反方向走。问所有蚂蚁都落下木棍的最快时间和最慢时间。
\end{example}
\begin{Mind}{蚂蚁过河问题}{}
最短时间：所有蚂蚁朝同一个方向运动。最长时间，蚂蚁碰撞后掉头可以认为蚂蚁还是朝着各自的方向走。例如L为5,蚂蚁a和b在两端分别朝中间走，那么他们会相撞。之后各自返回，这里如果认为蚂蚁还是朝着原来的方向走（没有返回，实际上可以理解为碰撞后蚂蚁互换了身份，从时间的角度考虑不会有影响）。这时花费的最大时间就是蚂蚁走的最大时间。
\end{Mind}
\begin{longlisting}
	\caption{蚂蚁过河问题}
	\cppfile[firstline=7,lastline=23]{third_party/coding/cxx/algorithm/common/src/antTime.cc}
	\label{code:antTime}
\end{longlisting}
\subsection{找到数组中出现次数大于数组长度一半的数}
\begin{Mind}{找到数组中出现次数大于数组长度一半的数}{}
对于数组中出现次数大于数组长度一半的数必定有\textbf{它出现的次数大于其它所有数字出现的次数}：对数组遍历如果数组元素和当前元素相等，次数times+1,不相等times-1,times不能为负数，如果times为0后下一个数字和当前保存的数字不相等则当前数字更新为此时的值，同时times为1。最后一个出现次数大于1的数有可能是目标，有可能不是，所以还需要对该元素判断是否出现次数大于出现次数的一半\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{graterhalf}
	\caption{出现次数大于数组长度一半}
\end{figure}
\begin{longlisting}
	\caption{出现次数大于数组长度一半的数}
	\cppfile[firstline=6,lastline=33]{third_party/coding/cxx/algorithm/common/src/getValue.cc}
	\label{code:getValue}
\end{longlisting}
该算法时间复杂度为$O(n)$，空间复杂度为$O(1)$

\subsection{寻找无序数组中的第k大元素}
先对前k个元素构建堆，遍历数组和堆顶元素比较，如果小于等于堆顶元素，则继续遍历，如果大于等于堆顶，则取代堆顶元素并调整堆。例如\figref{fig:min_ks}，找出最小的5个数。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{min_ks}
	\caption{第k大的数过程(最小堆)}
	\label{fig:min_ks}
\end{figure}
将数组[7,5,15,3,17,2,20,24,1,9,12,8]中的前5个元素构建堆，最终的堆顶元素就是要找的第k大的数。
建堆的时间复杂度$O(k)$,遍历剩余数组的时间复杂度为$O(n-k)$，每次调整堆的时间复杂度为$O(log(k))$最坏情况下时间复杂度$O((n-k)logk+k)$当当k远小于n的情况下可以近似认为$O(nlog(k))$。空间复杂度为$O(1)$（原地交换需要一个临时变量）。最小堆构建如\figref{fig:min_kth}。在实际的实现中我们不用构建最小堆，直接通过优先队列实现即可。
TODO: kth重构
\subsection{输出最小的k个数}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{min_kth}
	\caption{最小前k个数处理流程}
	\label{fig:min_kth}
\end{figure}
\begin{Mind}{第k大的元素}{}
如果我们使用 partition 对数组操作，轴值坐标左边的元素全小于轴值,右边全大于轴值。那么如果左边的元素正好为k就可以输出最小的k个数。如果左边的元素大于k，下次应该在坐标划分，否则应该在右边划分。先选轴值为最左边。
\end{Mind}
\begin{longlisting}
	\caption{Partion第k大的数}
	\cppfile[firstline=7,lastline=47]{third_party/coding/cxx/algorithm/common/src/smallestK.cc}
	\label{code:smallestK}
\end{longlisting}
时间复杂度O(n)。
\subsection{有效的数独}
\begin{example}[有效的数独]
请你判断一个 $9 \times 9$ 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
\begin{itemize}
	\item 数字 1-9 在每一行只能出现一次。
	\item 数字 1-9 在每一列只能出现一次。
	\item 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
\end{itemize}
\end{example}
\begin{Mind}{有效数独}{}
核心是检查行、列、块是否有重复的数字。算法实现上有两个常见做法：
\begin{enumerate}
	\item 遍历3遍，分别检查行、列、块是否符合要求。存储一行，遍历三遍。
	\item 遍历以便，分别更新行、列、块对应的值。存储翻了三倍，遍历一遍。
\end{enumerate}
\end{Mind}
上述两种算法时间复杂度和空间复杂度均为O(1)。这里\coderef{code:isValidSudoku}实现第一种。
\begin{longlisting}
	\caption{有效数独}
	\cudafile[firstline=5,lastline=47]{third_party/coding/cxx/algorithm/common/src/array_common.cc}
	\label{code:isValidSudoku}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/maximum-subarray/description/}{最大子数组和}}
\begin{example}[最大子数组和]
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

 

示例 1：
\begin{Textcode}
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
\end{Textcode}

\end{example}
\begin{Mind}{最大子数组和}{}
	求和过程中一旦发现当前求和结果为负数，则说明加上当前元素导致了结果为负数，此时为了获取更大值只能在此元素之后的元素通过求和获得最大值。
\end{Mind}
初始化求和为当前数组第一个元素，当前值为0，然后遍历数组：
\begin{enumerate}
	\item 如果当前数组元素和当前元素求和结果为正数，则意味着加上此元素有可能拿到最大数组和。加上数组元素并更新最大数组和。
	\item 如果当前数组元素和当前元素求和结果为负数则意味加上了过大的负数，不可能以之前的求和获得更大和了，从下一个位置尝试找到最大和。
\end{enumerate}
\begin{longlisting}
	\caption{最大子数组和}
	\cppfile[firstline=5,lastline=13]{third_party/coding/cxx/algorithm/common/src/maxSubArray.cc}
	\label{code:maxSubArray}
\end{longlisting}
\section{字符串}
\subsection{KMP算法}
部分匹配表(PMT)：\textbf{前缀表达式}\footnote{字符串除了最后一个字符外所有可能的顺序字符组合}和\textbf{后缀表达式}\footnote{字符串除了第一个字符外前面所有字符的顺序组合}的交集的最大长度。
\begin{figure}
	\centering
	\includesvg[width=0.6\textwidth]{kmp_match1}
	\caption{kmp匹配过程(找到失配位置)}
	\label{fig:kmp_match1}
\end{figure}
匹配字符串的PMT计算如\tabref{tab:PMT_computer}，
\begin{table}
	\centering
	\caption{计算部分匹配表}
	\begin{tabular}{p{0.2\textwidth}p{0.3\textwidth}p{0.3\textwidth}p{0.1\textwidth}}
		\toprule
		字符串      & 前缀字符串                                                     & 后缀字符串                                                     & 交集长度 \\
		\midrule
		A        & 无                                                         & 无                                                         & 0    \\
		AB       & B                                                         & A                                                         & 0    \\
		ABA      & \textcolor{red}{A}, AB                                    & \textcolor{red}{A}, BA                                    & 1    \\
		ABAB     & A, \textcolor{red}{AB}, ABA                               & B, \textcolor{red}{AB}, BAB                               & 2    \\
		ABABA    & \textcolor{red}{A}, AB, \textcolor{red}{ABA}, ABAB        & \textcolor{red}{A}, BA, \textcolor{red}{ABA}, BABA        & 3    \\
		ABABAB   & A, AB, ABA, \textcolor{red}{ABAB}, ABABA                  & B, AB, BAB, \textcolor{red}{ABAB}, BABAB                  & 4    \\
		ABABABC  & A, AB, ABA, ABAB, ABABA, ABABAB                           & C, BC, ABC, BABC, ABABC, BABABC                           & 0    \\
		ABABABCA & \textcolor{red}{A}, AB, ABA, ABAB, ABABA, ABABAB, ABABABC & \textcolor{red}{A}, CA, BCA, ABCA, BABCA, ABABCA, BABABCA & 1    \\
		\bottomrule
	\end{tabular}
	\label{tab:PMT_computer}
\end{table}
即可得到PMT[0,0,1,2,3,4,0,1]。根据\figref{fig:kmp_match1}匹配到索引为6的元素时$Target(A) \neq Pattern(C)$这时Target之前的PMT[j-1]前5个元素与Pattern的0到PMT[j-1]位相同，即(ABABAB=ABABAB)。这是因为字符串Target在 i 位失配，也就意味着 Target [i−j,i] 这一段是与模式字符串的 [0,j] 这一段是完全相同的。而我们上面也解释了，字符串Pattern从 0 到 j−1 ，在这个例子中就是”ABABAB”，其前缀集合与后缀集合的交集的最长元素为"ABAB"， 长度为4。所以就可以断言，Target字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可。
\begin{figure}
	\centering
	\includesvg[width=0.5\textwidth]{kmp_match2}
	\caption{KMP 匹配跨越移动}
	\label{fig:kmp_match2}
\end{figure}

简言之，以\figref{fig:kmp_match2}中的例子来说，在 i（6） 处失配，那么Target字符串和Pattern字符串的前边6位就是相同的。又因为Pattern字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知Target字符串i之前的4位和Pattern字符串开头的4位是相同的。

我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j 位失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，所以为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next数组如\tabref{tab:next_array}。
\begin{table}
	\centering
	\caption{next数组}
	\begin{center}
		\begin{tabular}{p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.05\textwidth}p{0.05\textwidth}p{0.05\textwidth}p{0.05\textwidth}p{0.05\textwidth}}
			\toprule
			索引   & 0  & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
			\midrule
			字符   & A  & B & A & B & A & B & C & A \\
			PMT  & 0  & 0 & 1 & 2 & 3 & 4 & 0 & 1 \\
			% next(特定算法) & -1 & 0 & 0 & 1 & 2 & 3 & 4 & 0 \\
			\bottomrule
		\end{tabular}
	\end{center}
	\label{tab:next_array}
\end{table}

% 现在，我们再看一下如何编程快速求得next数组。其实，求next数组的过程完全可以看成字符串匹配的过程，即以Pattern字符串为Target字符串，以Pattern字符串的前缀为Target字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。如\figref{fig:PMT}，这里以next(6)的计算为例，因为next[0]=-1,计算next[1]为A的前后缀的交集的最大长度0，next[2]为AB前后缀交集最大长度0，next[6]为的前缀为A、AB、ABA、ABAB、ABABA后缀为B、AB、BAB、ABAB、BABAB。交为ABAB长度为4。
% \begin{figure}[!htbp]
% 	\centering
% 	\includesvg[width=\textwidth]{PMT}
% 	\caption{对应的位置关系}
% 	\label{fig:PMT}
% \end{figure}
% \[P[0:k-1] = P[j-k:j-1],k=1,j=3\]
% 因为当$T[i]\neq P[j],C\neq D$时$T[i-j:i-1] == P[0:i-1]$，由$P[0:k-1] = P[j-k:i-1](ABA=ABA)$必然有：$T[i-k:i-1] = P[0:k-1],A=A$。通常将每个位置j对应的值k放入next[ ]数组。k实际上为第一个不匹配的字符所在位置的左边字串的两边相等的元素。如何求这里的k？
% \begin{figure}[!htbp]
% 	\centering
% 	\includegraphics[width=0.5\textwidth]{kmp4}
% 	\caption{第一个字符就不匹配}
% 	\label{fig:kmp_4}
% \end{figure}

% \figref{fig:kmp_4}这时候第一个字符串不匹配，匹配字符串为0,匹配字符串左边和右边相等的元素个数不存在，这里初始化为-1,即next[0] = -1。
% \begin{figure}[!htbp]
% 	\centering
% 	\includegraphics[width=0.5\textwidth]{kmp5}
% 	\caption{字符串第二个字符不匹配}
% 	\label{fig:kmp_5}
% \end{figure}
% next vector实现用于调试查看代码执行流程。
\begin{longlisting}
	\caption{KMP next查找}
	\cppfile[firstline=3,lastline=21]{third_party/coding/cxx/algorithm/common/src/kmp.cc}
	\label{code:kmpNext}
\end{longlisting}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{kmp_next}
	\caption{next计算示意图}
	\label{fig:kmp_next}
\end{figure}
\figref{fig:kmp_next} 计算索引的前缀字串：
\begin{itemize}
	\item 最初情况，前缀字串长度为preLen = 0，然后next数组n[0]=0。
	\item a和preLen指向的元素(a)相等则next[1] = 1，preLen=1此时n[1]=1。
	\item b和preLen指向元素不像等(a)，preLen-=1（\coderef{code:kmpNext}中9行16行），之后preLen=0然后设置此时位置n[i] = 0。
	\item a和preLen指向元素相等(a)，结果为preLen+=1，preLen=1，此时n[3]=1（\coderef{code:kmpNext}中9行）。
	\item a和preLen指向相等相等(a)，结果为preLen+=1，preLen=2，此时n[4]=2。
	\item a和preLen指向不像等(b)，preLen -= 1此时preLen = 1，此时preLen指向的元素(a)和当前元素a相等，n[5] = preLen+1=2。
	\item c和preLen指向不相等。结果preLen-1，之后preLen指向的元素和当前依然不像等直到preLen=0设置n[6] = 0。
\end{itemize}
\coderef{code:kmp}实现中，return放在了循环中，一旦发现直接返回结果，也可以直接跳出然后返回结果。
\begin{longlisting}
	\caption{KMP 实现}
	\cppfile[firstline=23,lastline=42]{third_party/coding/cxx/algorithm/common/src/kmp.cc}
	\label{code:kmp}
\end{longlisting}
%\begin{longlisting}
%	\caption{kmp}
%	\cppfile[firstline=1,lastline=41]{code/string/kmp/main.cpp}
%	\label{code:kmp}
%\end{longlisting}


% 这时候第一个不匹配的字符串的左边的字符串为a，长度为1.不存在其左右字符相等，这时候next[1] = 0;
% \begin{figure}[!htbp]
% \centering
% \includegraphics[width=0.5\textwidth]{kmp5}
% \caption{P[k] = P[j]}
%     \label{fig:kmp_7}
% \end{figure}
% 
% 当$P[k]=P[j]$时，有$next[j+1] = next[j]+1$,这是因为在$P[j]$之前已经有$P[0:k-1] = p[j-k:j-1],AB=AB$,这时候$P[k] = P[j],C=C$，我们是不是可以得到$P[0:k-1]+P[k]=p[j-k:j-1]+P[j],ABC=ABC$。即$P[0:K] = P[j-k:j]$即$next[j+1]=k+1=next[j]+1$。
% 如果$P[k]\neq P[j]$则$k = next[k]$。
% 
% 看上面的例子，我们已经不可能找到ABAB这个最长的串了，但是我们还是可能找到[A,B],[B]这样的串。所以这个过程不像再定位[A,B,A,C]这个串，当C和主串不一样了（也就是k位置不一样了），那当然是把指针移动到next[k]。
% \begin{figure}[!htbp]
% \centering
%     \subfigure[字符串]{\includegraphics[width=0.4\textwidth,height=1.5cm]{kmp1.png}}
%     \subfigure[匹配]{\includegraphics[width=0.4\textwidth,height=1.5cm]{kmp2.png}}
%     \label{fig:kmp_7}
% \end{figure}
% 从匹配的结果看：
% \[t_{i-j}\quad t_{i-j+1} \quad t_{i-j+2}\quad t_{i-1} = p_0\quad p_1\quad p_2\cdots p_{j-1}\]
% 朴素匹配的下一趟
% \[p_0\qquad p_1 \cdots p_{j-2}\neq p_1\qquad p_2\qquad\cdots p_{j-1}\]
% 字符串的特征向量构造方法:
% \begin{equation*}
%     next[j]=\begin{cases}
%         -1\quad j=0\\
%         max\left\{k:0<k<j\&p[0\cdots k-1]=p[j-k\cdots j-1] \right\}\\
%         0\quad 其它
%     \end{cases}
% \end{equation*}
% 计算字符串的模式匹配字符串P = a a a a b a a a a c,计算j对应位置的前一位j-1子序列的真子序列相等的最大长度。
% \begin{itemize}
% \item j=0,next[0] = -1
% \item j=1,0<k<j,k没有值，next[1] = 0
% \item j=2,k=1,next[2] = 1
% \item j=3,k=1,2,next[3] = 2
% \item j=4,k=1,2,3,next[4] = 3
% \item j=5,k=1,2,3,4,next[5] = 0
% \item j=6,k=1,2,3,4,5,next[6] = 1
% \item j=7,k=1,2,3,4,5,6,next[7] = 2
% \item j=8,k=1,2,3,4,5,6,7,next[8] = 3
% \item j=[9],k=1,2,3,4,5,6,7,next[9] = 4
% \end{itemize}
% \begin{figure}[!htbp]
% \centering
% \includegraphics[width=\textwidth]{kmp3.png}
%     \label{fig:kmp_8}
% \caption{kmp匹配示意图}
% \end{figure}
% \begin{figure}[!htbp]
% \centering
% \includegraphics[width=\textwidth]{kmp3.png}
% \caption{kmp匹配示意图
% \end{figure}
% \textbf{求解特征向量的算法框架}\\
% 特征数$n_j(j>0,0\leq n_{j+1} \leq j)$是递归定义的：
% \begin{enumerate}
% 	\item $n_0=-1$,对于j>0的$n_{j+1}$,假定已知前一位的特征数$n_j$，令$k=n_j$
% 	\item 当$k\geq 0$且$p_j\neq p_k$时，则令$k = n_k$;让步骤2循环到条件不满足
% 	\item $n_{j+1}$ 此时k == -1或者 $p_j == p_k$
% \end{enumerate}
% kmp算法框架：
% \begin{enumerate}
% 	\item 分别从target和parttern第一位开始向后依次匹配。找到第一位失配的位置。将parttern第next[i]位移动到失配位置。
% 	\item 如果失配出现在parttern第一位则将next[0]移动到失配位置。因为next[0]为-1。将-1移动到失配位置，这时候相当于字符串整体右移一格。
% 	\item 如果匹配到整个parttern末尾，说明匹配，返回位置为target指向的位置和parttern指向位置的差。
% \end{enumerate}
% TODO: 精简bing重构KMP算法
%\begin{longlisting}
%	\caption{kmp算法}
%	\cppfile[firstline=1,lastline=66]{code/string/ex4/main.cpp}
%	\label{code:kmp}
%\end{longlisting}

\subsection{回文子串}
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
\begin{Textcode}
	输入：s = "abc"
	输出：3
	解释：三个回文子串: "a", "b", "c"
\end{Textcode}
\begin{Mind}{回文子串}{}
	对于奇数长度的回文串，回文中心为中间元素，比如abc的回文中心为b，偶数则为中间两个元素，例如abbc的回文中心为b、b。长度为3的字符串回文中心可以为：
\end{Mind}
\begin{table}
	\caption{回文子串的扩展中心}
	\begin{center}
		\begin{tabular}{ccc}
			\toprule
			子串  & 左回文起点 & 右回文起点 \\
			\midrule
			a   & 0     & 0     \\
			b   & 1     & 1     \\
			c   & 2     & 2     \\
			ab  & 0     & 1     \\
			bc  & 1     & 2     \\
			abc & 2     & 2     \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table}
长度为n的字符有$2\times n-1$个字符串。偶数长度的字符串的起点和终点分别是n/2、n/2+n\%1。我们只需要在$0-2\times n-2$中的2n-1个可能起始点左右扩展，如果发现回文串则+1。实现如\figref{code:countSubstrings}。
\begin{longlisting}
	\caption{回文子串}
	\cppfile[firstline=3,lastline=16]{third_party/coding/cxx/algorithm/common/src/countSubstrings.cc}
	\label{code:countSubstrings}
\end{longlisting}
\subsection{替换字符串中的指定字符}
比如We are happy中的空格替换成We\%20are\%20happy。
\begin{Mind}{替换字符串中特定字符}{}
	遍历字符串获取字符串空格数量，设置两个指针P1一个指向字符串的结尾，一个指针P2指向拟插入字符后的空间的末尾（这里有两个空格，则插入到P1后面+4的位置）将P1指向的内容一个个往后移动P2指向的最后，如果遇到空格P2指针移动到移动字符串(Happy)的前面,在此插入\%20,同时移动指针P2的位置。重复操作直到两个指针指向的位置相等即可停止。
\end{Mind}
\begin{algorithm}
	\caption{替换字符串算法}
	\begin{algorithmic}
		\REQUIRE 字符串长度能够容纳添加空格后的字符串。P1指向字符串尾部，P2指向插入字符串后的尾部。
		\WHILE{P1指针指向位置和P2指向位置不同}
		\STATE 往字符串最后面移动非空格字符串，指针P2指向移动字符串后的前一个位置，同时插入待插入的字符串。
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}
整个算法过程：
\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{replace_string}
	\caption{替换空格算法过程}
\end{figure}
\begin{longlisting}
	\caption{替换空格}
	\cppfile[firstline=6,lastline=29]{third_party/coding/cxx/algorithm/common/src/replaceSpace.cc}
	\label{code:replaceSpace}
\end{longlisting}
\subsection{判断一个字符串是不是数值}
\begin{example}[判断一个字符串是不是数值]
	字符串是科学计数法表示的字符串如1.23e-3,或者1.23E-3
\end{example}
%TODO: 重构判断字符串是否为数值
%\cppfile[firstline=1,lastline=31]{code/offer/27/main.cpp}
\subsection{处理重复字符串}
要求输入字符串中XXYY类被处理为XXY，但是像AABBCC包含有两个XXYY，分别为AABB和BBCC这样只处理AABB。XXX被处理为XX。
\begin{Mind}{处理重复字符串}{}
这里先判断是不是XXX类型，如果是就删除第一个X，这样XXX就被处理成了XX。然后判断是不是XXYY，如果是则删除第三个元素Y。从字符串开始判断直到判断结束。
\end{Mind}
TODO: 处理重复字符串，重构
%\cppfile[firstline=1,lastline=22]{code/arith/ex95/main.cpp}
\subsection{字符串中的第一个唯一字符的索引}
\begin{example}[字符串中的第一个唯一字符]
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0
\end{example}
\begin{longlisting}
	\caption{字符串中第一次出现且唯一出现过一次的字符索引}
	\cudafile[firstline=7,lastline=20]{third_party/coding/cxx/algorithm/common/src/firstUniqChar.cc}
	\label{code:firstUniqChar}
\end{longlisting}

\subsection{字符串转换整数 (atoi)}
\begin{example}[字符串转换整数 (atoi)]
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

函数 myAtoi(string s) 的算法如下：
\begin{itemize}
	\item 空格：读入字符串并丢弃无用的前导空格（" "）
	\item 符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
	\item 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
	\item 舍入：如果整数数超过 32 位有符号整数范围 [$-2^{31}$,  $2^{31}$ - 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 $-2^{31}$ 的整数应该被舍入为 $2^{31}$ ，大于 $2^{31} - 1$ 的整数应该被舍入为 $2^{31} - 1$ 。
\end{itemize}
\end{example}
\begin{Mind}{字符串转换整数}{}
从前到后扫描字符，如果是空字符则往后跳过。直到找到'+'或者'-'符号为止。然后将字符获取到通过res=10*res+v更新数值。这里唯一需要注意的问题是res可能会溢出。这里需要注意的是int的最大值为：2147483647，最小值为:-2147483648，出分为两种情况：
\begin{itemize}
	\item 10*res溢出
	\item 10*res+v溢出
\end{itemize}
\end{Mind}
\begin{longlisting}
	\caption{字符串转换为整数}
	\cudafile[firstline=3,lastline=30]{third_party/coding/cxx/algorithm/common/src/myAtoi.cc}
	\label{code:myAtoi}
\end{longlisting}
\coderef{code:myAtoi} 25行注释行的写法不对，原因在于对于较大的数：如果先加上一个数可能会导致溢出，所以先加后减结果不对。
\section{区间问题}
\subsection{汇总区间}
给定一个  无重复元素 的 有序 整数数组 nums 。返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。列表中的每个区间范围 [a,b] 应该按如下格式输出：
\begin{itemize}
	\item "a->b" ，如果 a != b。
	\item "a" ，如果 a == b。
\end{itemize}
示例：
\begin{Textcode}
	输入：nums = [0,2,3,4,6,8,9]
	输出：["0","2->4","6","8->9"]
	解释：区间范围是：
	[0,0] --> "0"
	[2,4] --> "2->4"
	[6,6] --> "6"
	[8,9] --> "8->9"
\end{Textcode}
\begin{Mind}{区间汇总思路}{}
	实现上使用双指针容易理解，不太好处理的是指向同一个元素如何处理。这里采用的办法是right+1的值是否比当前大（即只有条件满足后right=right+1），这样就能避免直接更新right指针导致left和right指向同一个元素难以处理。值得注意的是左右值是否相差1通过nums[right + 1] == current + 1比较而不是nums[right + 1] - current == 1。因为后者current为负数的时候容易超过数值边界。实现\coderef{code:summaryRanges}。
\end{Mind}
\begin{longlisting}
	\caption{区间汇总实现}
	\cppfile[firstline=2,lastline=31]{third_party/coding/cxx/algorithm/common/src/summaryRanges.cc}
	\label{code:summaryRanges}
\end{longlisting}
\subsection{用最少数量的箭引爆气球}
\begin{example}[用最少数量的箭引爆气球]
	有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [$x_{start}$, $x_{end}$] 表示水平直径在 $x_{start}$ 和 $x_{end}$之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  $x_{start} \leq x \leq x_{end}$，则该气球会被 引爆 。可以射出的弓箭的数量没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2

解释：如\figref{fig:findMinArrowShots}，1-6、2-8之间的用一段公共区域，箭穿过此区域能一下引爆两个气球。1-2这个射箭则只能引爆1-6这个区间的气球，6-8这个区间只能引爆2-8这个区间的气球。同理10-12这个区间射箭能引爆两个气球。整体最小弓箭数为2。
\begin{itemize}
	\item 在x = 6处射出箭，击破气球[2,8]和[1,6]。
	\item 在x = 11处发射箭，击破气球[10,16]和[7,12]。
\end{itemize}
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{findMinArrowShots}
	\caption{用最少数量的箭引爆气球}
	\label{fig:findMinArrowShots}
\end{figure}
\begin{Mind}{用最少的箭引爆气球}{}
	和区间合并类似，当气球重叠的越多，引爆气球需要的射箭数就越少。所以只需要找到所有重叠区域的公共区域统计其数量即可。所有重叠区域和区间合并类似，不同在于区间的下界是重叠区域的最大值，上界是重叠区域的最小值。
\end{Mind}
\begin{longlisting}
	\caption{用最少的箭引爆气球}
	\cudafile[firstline=3,lastline=16]{third_party/coding/cxx/algorithm/common/src/findMinArrowShots.cc}
	\label{code:findMinArrowShots}
\end{longlisting}

\subsection{区间插入}
\begin{example}[区间插入]
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
\end{example}
\begin{Mind}{区间插入}{}
遍历区间找到合适的位置将新的区间插入。然后融合插入新区间之后的结果。
\end{Mind}
代码实现\coderef{code:insertRange}。
\begin{longlisting}
	\caption{区间插入}
	\cppfile[firstline=100,lastline=114]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:insertRange}
\end{longlisting}

\subsection{是否可以参加所有会议}
给定一系列的会议时间间隔，包括起始和结束时间$[[s_1,e_1],[s_2,e_2],\ldots (s_i < e_i)$，确定一个人是否可以参加所有会议。
\begin{example}
	给定区间=[[0,30]，[5,10]，[15,20]]，返回false。
\end{example}
\begin{Mind}{会议问题思路}{}
	将起始、终止对按照起始时间点从小到大排序。时间对第一个元素为起始时间，第二个为终止时间。对第一对（排序保证了起始时间最小），终止时间肯定大于起始时间。这时候起始时间变成第一对的终止时间end，开始看第二对，如果第二对起始时间小于当前的终止时间，表明第二对时间和第一对重复了，那就是产生冲突无法参加两个会议。否则将第二对的终止时间给终止时间end。
\end{Mind}
\begin{longlisting}
	\caption{是否能参加所有会议}
	\cppfile[firstline=2,lastline=12]{third_party/coding/cxx/algorithm/common/src/isAttention.cc}
	\label{code:isAttention}
\end{longlisting}

\subsection{所需会议室}
给定一系列的会议时间间隔intervals，包括起始和结束时间$[[s_1,e_1],[s_2,e_2],...] (s_i < e_i)$，找到所需的最小的会议室数量。给出 intervals = [(0,30),(5,10),(15,20)], 返回 2。
\begin{Mind}{扫描线算法}{}
扫描线算法：
\begin{itemize}
	\item 将所有区间从小到大排列。
	\item 将排列的区间起点设置为1，终点设置为-1。
	\item 扫描整个区间，求出和最大的数为结果。
\end{itemize}
\end{Mind}
扫描线算法示意图如\figref{fig:scan_line}
\begin{figure}
	\centering
	\includegraphics[width=\textwidth]{scan_line}
	\caption{所需会议室（扫描线算法）示意图}
	\label{fig:scan_line}
\end{figure}
代码如\coderef{code:countRoom}。
\begin{longlisting}
	\caption{所需会议室}
	\cppfile[firstline=3,lastline=17]{third_party/coding/cxx/algorithm/common/src/countRoom.cc}
	\label{code:countRoom}
\end{longlisting}

\subsection{区间融合}
\begin{example}[区间融合]
	给出一个区间的集合，请合并所有重叠的区间。示例 1:

	输入: [[1,3],[2,6],[8,10],[15,18]]
	输出: [[1,6],[8,10],[15,18]]
	解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

	示例 2:
	输入: [[1,4],[4,5]]
	输出: [[1,5]]
	解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
\end{example}
\begin{longlisting}
	\caption{区间融合}
	\cppfile[firstline=99,lastline=113]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:mergeSpan}
\end{longlisting}

\section{双指针问题}
\subsection{长度最小的数组}
\begin{example}[长度最小的数组]
给定一个含有 n 个正整数的数组和一个正整数target。找出该数组中满足其和 $\geq$ target 的长度最小的 连续子数组 $[nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r]$ ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
\end{example}
\begin{Mind}{长度最小的子数组}{}
	指定数组的起点start、end。记录[start,end]区间的数值的和sum，如果$sum\geq target$则start指针左移和减少，否则end右移和变大，长度为end-start+1。直到end=start。
\end{Mind}

\begin{longlisting}
	\caption{长度最小的数组}
	\cppfile[firstline=3,lastline=21]{third_party/coding/cxx/algorithm/common/src/minSubArrayLen.cc}
	\label{code:minSubArrayLen}
\end{longlisting}


\subsection{滑动窗口的最大值}
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
\begin{Textcode}
	输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
	输出: [3,3,5,5,6,7]
	解释:

	滑动窗口的位置                最大值
	---------------               -----
	[1  3  -1] -3  5  3  6  7      3
	1 [3  -1  -3] 5  3  6  7       3
	1  3 [-1  -3  5] 3  6  7       5
	1  3  -1 [-3  5  3] 6  7       5
	1  3  -1  -3 [5  3  6] 7       6
	1  3  -1  -3  5 [3  6  7]      7

\end{Textcode}
\begin{Mind}{滑动窗口的最大值}{}
	两个相邻滑动窗之间有k-1个重复数字，我们将k个数字加入最大堆。堆顶元素就是最大值，接着滑动的时候将新的数字加入最大堆，此时如果加入的数字$\leq maxHeap.top()$中的元素，这意味着加入此元素不会影响最大堆调整。反之该元素将在堆顶。最大堆能保证堆顶元素是最大的，但是不能保证堆顶元素在滑动窗边界以内，所以我们判断最大值的时候需要对top的索引和当前索引计算一下间距$i-k\geq 3$的元素都应该丢掉（不在滑动窗以内）。
\end{Mind}

\begin{longlisting}
	\caption{滑动窗口的最大值}
	\cppfile[firstline=3,lastline=18]{third_party/coding/cxx/algorithm/datastruct/src/maxSlidingWindow.cc}
	\label{code:maxSlidingWindow}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度$O(nlog(n))$。
	\item 空间复杂度$O(n)$
\end{itemize}
本问题的难点在于如何用$O(1)$获取k个元素中最大的元素。我们可以维护一个单调队列，保证队列顶部的元素是队列中最大元素，这样每次滑动窗滑动的时候引入的新的数值和对头的元素对比即可。这样就能以O(1)访问滑窗中的最大值了。以上面的例子为例：
\begin{enumerate}
	\item 假设滑动窗左边还有两个元素，覆盖的元素中1最大，入队列，滑动一格3入队列。
	\item 3比1大，1出队列3入队列，滑动一格，-1入队列。
	\item 此时队列元素正好为3，将队头元素加入结果，右移一格-3入队列。
	\item 3最大，3加入结果然后右移一格5入队列。
	\item 5比队列头元素大，将队列出队，然后将5入队列，同时添加到结果中。右移一格3入队列。
	\item 3比5小，5加入结果右移一格6入队列。
	\item 6比队头元素5大，队列元素出队，6入队，右移一格，7加入。
	\item 7比队头元素大，6出队7入队，7加入结果。
\end{enumerate}

\subsection{\href{https://leetcode.cn/problems/3sum-closest/description/}{最接近的三个数之和}}
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。
\begin{Textcode}
	输入：nums = [-1,2,1,-4], target = 1
	输出：2
	解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
\end{Textcode}
\begin{Mind}{最接近的三个数之和}{}
	先对数组进行排序，初始化前三个元素和，然后固定每个元素，从它最右边第一个比它大的数left（索引）开始到最后一个最大的数求和，如果结果比初始值更接近target则更新这个结果，然后对比当前和与target关系，如果<target则更接近需要右移左指针，同理左移右指针最后指针相遇为止。
\end{Mind}
\begin{enumerate}
	\item 排序得到[-4,-2,1,2]。对第一个元素-4，找到其右边第一个大于其的元素位置left（此时值为-2）和最大元素位置right求和（结果-4）计算 距离后更新最小距离和此时的和。
	\item 此时因为三数和sumValue<target，想要缩短差距left只能右移。
	\item 左移后三数之和-1，距离为2，更新ans。此时sumValue<target，继续右移，碰到right，跳出。此时-4开头能得到的最小距离更新为-1。走到-2继续上面的操作。
\end{enumerate}
\begin{longlisting}
	\caption{最接近的三个数之和}
	\cppfile[firstline=2,lastline=26]{third_party/coding/cxx/algorithm/common/src/threeSumClosest.cc}
	\label{code:threeSumCloses}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度：$O(n^2)$
	\item 空间复杂度：$O(1)$
\end{itemize}

\subsection{数组中三个数的和为0}
\begin{example}[数组中三个数的和为0]
	给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
	注意：答案中不可以包含重复的三元组。

	示例：

	给定数组 nums = [-1, 0, 1, 2, -1, -4]，

	满足要求的三元组集合为：
	[
	[-1, 0, 1],
	[-1, -1, 2]
	]
\end{example}

\begin{Mind}{三数和}{}
	对数组排序，然后遍历排序后的数组，获取元素，如果当前元素大于0则直接返回结果。（最小的数都大于0，无论如何都不可能通过加上两个更大的数变成0）。否则用左右指针分别指向当前元素的下一个元素和最后一个元素。对三个数求和：
	\begin{itemize}
		\item 三个数之和等于0，表示已经找到和为0的三个数。左指针右移，右指针左移。（左指针右移会使和大于0，右指针左移可能会使和小于0）直到两个指针指向同一个元素停止。开始当前元素右移一位进行下一轮判断。
		\item 如果三个元素和大于0，只能右指针左移以减小和达到为0的结果。
		\item 如果三个数和小于0，只能增加左指针达到为0的结果。
	\end{itemize}
	这里需要注意的是左右指针会遇到同样的元素，比如我们已经知道（-4）+（-1）+（2）不为0，左指针右移的结果还是（-4）+（-1）+（2）这时候求和已经没有必要，所以左指针直接右移，对于右指针也是这样。当前元素如果发现了和为0的组合，如果下一个元素和当前元素相同也没有求和的必要，因为之前已经求过了。
\end{Mind}
排序数组最快$O(n(logn))$，遍历数组$O(n)$,遍历当前元素后左右移动指针$(O(n^2))$,时间复杂度为：$O(n^2)$，空间复杂度为$O(1)$。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{threeSum}
	\caption{求和示意图}
	\label{fig:threeSum}
\end{figure}
\begin{enumerate}
	\item 初始状态下，当前元素为-4，左右指针指向-1，2。（因为初始元素小于0，所以需要左右指针），和-3，所以需要左指针右移以加大和达到0。
	\item 左指针右移之后元素和上一次计算相同，左指针直接右移，直到左右指针指向末尾元素2遍历结束，说明当前元素为-4的时候没法找到和为0的元素，进行下一步比较。
	\item 当前元素为-1，（-1）+（-1）+2==0，找到结果，加入结果列表。左指针指右移，右指针左移。找到（-1）+（0）+（1）==0，找到结果加入结果列表，直到左右指针同时指向0元素为-1的时候遍历完成。
	\item 当前元素为-1，和上一步的元素相同，不用比较直接到下一个元素0。
	\item 当前和为大于0，只能左移右指针，左右指针同时指向1结束。
	\item 当前元素为1，已经大于0所以直接结束。
\end{enumerate}
\begin{longlisting}
	\caption{三个数的和}
	\cppfile[firstline=6,lastline=39]{third_party/coding/cxx/algorithm/common/src/threeSum.cc}
	\label{code:threeSum}
\end{longlisting}

\subsection{装水最多的容器}
\begin{example}[装水最多的容器]
给你 n 个非负整数 $a_1,a_2,\ldots,a_n$，每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$ 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
\end{example}
\begin{figure}
	\centering
	\includegraphics[width=0.4\textwidth]{maxArea}
	\caption{盛水最多的容器示意图}
	\label{fig:maxArea}
\end{figure}
\begin{Mind}{盛水最多的容器}{}
Water=min(height[left],height[right])*(right-left) 盛水多少主要与容器高度和容器间隔(left-right)有关，装水量由左右两边容器中更短min(height[left],height[right])的容器决定。在 (right-left) 最大的时候想装最多的水，
只能依靠移动left或者right抵消(right-left)的减小，即移动左右的同时保证增加min(height[left],height[right])。最开始情形左右 left 和 right装水(8-0)*1=8,现在希望获得更多的水则只能移动短的left容器使得找到height[1] = 8。这时候容器中的水$(8-1)*7=49$ 宽度减少了1,但是因为最短容器变大导致装水更多。这时候我们需要和刚才一样的方法移动短边以希望增大盛水量（left和right的高度需要判断一下谁更小，决定移动，left只能往右边移动，right只能往左边移动）。实现\coderef{code:maxArea}
\end{Mind}
\begin{longlisting}
	\caption{装水最多的容器}
	\cppfile[firstline=6,lastline=24]{third_party/coding/cxx/algorithm/common/src/maxArea.cc}
	\label{code:maxArea}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/maximum-subarray/description/}{最大子数组和}}
\begin{example}[子数组中和最大的值]
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
\end{example}

\begin{Mind}{求数组中子数组元素和最大值}{}
	对数组从第一个元素开始往后求和，如果和小于0,加上下一个元素肯定小于下一个元素，这样最大值肯定没有从下一个元素开始求和大。这样找到只要和不为负数就累加，否则下一个数作为和的第一个数。
\end{Mind}
实现如\coderef{code:maxSubArray}。
\begin{longlisting}
	\caption{子数组中的最大和}
	\cppfile[firstline=5,lastline=13]{third_party/coding/cxx/algorithm/common/src/maxSubArray.cc}
	\label{code:maxSubArray}
\end{longlisting}
\coderef{code:maxSubArray} 中current初始化为0，然后0<0肯定不满足条件，current就过渡到了数组元素。

\section{位运算问题}
\subsection{开关灯}
\begin{example}[开关灯]
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。找出并返回 n 轮后有多少个亮着的灯泡。
\end{example}
\begin{Mind}{开关灯}{}
	灯泡索引编号为1-n。假设其中编号为3的倍数被反转，1的时候被反转一次，3被反转一次。即：索引为k的矩阵反转的次数是其约数的个数（3的约数是1，3，6的约数是1，2，3，6）。k如果有约数x则一定有约数$\frac{k}{x}$，如果$x=\frac{k}{x}$则约数为偶数，否则为奇数。也就是说$k=\sqrt{x}$的结果就是奇数。因此我们只需要找出 $1,2,\cdots,n$ 中的完全平方数的个数即可，答案即为 $foor(\sqrt{n})$。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.4\textwidth]{bulbSwitch}
	\caption{开关灯示意图}
	\label{fig:bulbSwitch}
\end{figure}
\subsection{数组中只出现一次的两个数字}
\begin{example}[数组中只出现一次的两个数字]
找到数组中只出现一次的两个数字，同时输出的时候保证小数在前，大数在后。
\end{example}
\begin{Mind}{数组中只出现一次的两个数字}{}
	对于1、2、1我们知道出现一次的数字是2，我们可以通过异或运算找到数字$1\oplus2\oplus1=2$。所以如果找到只出现一次的数字则只需要将数组中的所有元素异或即可，
	这里需要找到两个只出现一次的数字。如果我们能把两个只出现一次的数放在两个分组中，分别求出分组中只出现一次的字符即可得到结果。如果数组中有两个数字不相同，那么将数组中的元素逐个异或最后能找到两个不同数字中哪个二进制位不同，比如：1、2、3、1。按位异或后结果为1，2和3的不同之出发生在0位。然后使用其和数组中数字按位\&根据得到的结果是0或者1区分不同的分组，然后再通过异或运算找到对应的数值。
\end{Mind}
\begin{longlisting}
	\caption{查找数组中两个只出现一次的数字}
	\cppfile[firstline=3,lastline=25]{third_party/coding/cxx/algorithm/common/src/findNumsAppearOnce.cc}
	\label{code:findNumsAppearOnce}
\end{longlisting}
\subsection{给定数字下最接近的2的次幂}
\begin{Mind}{给定数字下最接近的2的次幂}{}
对于任意给定的数字，先右移一位然后和自己or。这样就可以将数字最高位1的右边设置为1，我们的目标是将最高位右边所有的位都设置为1然后对结果+1就是最后的结果。
\end{Mind}
\begin{longlisting}
	\caption{给定元素其最接近的2的次幂}
	\cppfile[firstline=10,lastline=18]{third_party/coding/cxx/algorithm/common/src/isPowerOfTwo.cc}
	\label{code:isPowerOfTow}
\end{longlisting}
\coderef{code:isPowerOfTow} 中数值先减去1是为了放置数据本身就是2的次幂的情况。现在假设\textcolor{green}{1}100和1\textcolor{green}{0}11，我们分别右移一位然后和自己or得到结果：1\textcolor{red}{1}10和1\textcolor{red}{1}10

\section{设计部分}
\subsection{实现数据结构栈}
\begin{example}[实现最小栈数据结构]
	通过两个栈存放数据，m\_data,m\_min分别用来存放原始入栈数据和最小值。使得pop，push，min时间复杂度为O(1)
\end{example}
\begin{Mind}{最小栈}{}
构造两个栈，一个数据栈，一个最小栈。push的时候数据栈永远更新，最小栈根据情况，如果有更小的元素则最小栈直接push否则最小栈push栈顶最小元素。pop的时候数据栈和最小栈同时pop。
\end{Mind}
\begin{longlisting}
\caption{最小栈}
\cppfile[firstline=6,lastline=19]{third_party/coding/cxx/algorithm/common/src/MinStack.cc}
\label{code:miniStack}
\end{longlisting}

\subsection{用栈实现队列}
\begin{example}[用栈实现队列]
	栈是先入后出，队列是先入先出。用栈实现队列实现先入先出。
	\begin{itemize}
		\item push(x)：将一个元素放入队列的尾部。
		\item pop(x)：从队列首部移除元素。
		\item peek()：返回队列首部的元素。
		\item empty()：返回队列是否为空。
	\end{itemize}
\end{example}
通过两个栈实现将先入后出转化为先入先出。一个数据栈用了存放数据，一旦有peek操作，则将数据栈里面的元素放入另一个栈（第二个栈出栈实现先入先出）。
\begin{longlisting}
	\caption{栈实现队列}
	\cppfile{third_party/coding/cxx/algorithm/datastruct/src/MyQueue.cc}
	\label{code:implStackWithStack}
\end{longlisting}

\subsection{用队列实现栈}
\begin{example}[队列实现栈]
	用先入先出的队列实现先入后出的栈。
\end{example}
定义队列存储数据，入栈的时候如果队列为空则直接将元素如队列，否则将元素入队列之后将入队列之前的元素出队列然后重新入队。实现一个队列先入后出。push操作时间复杂度$O(n)$其它时间和空间复杂度都为$O(1)$。
\subsection{LRU缓存}
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类：
\begin{itemize}
	\item LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。
	\item int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
	\item void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该删除最久未使用的关键字。
\end{itemize}
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
\begin{Mind}{LRU缓存实现}{}
	双向链表和hashmap。首先双向双向链表用来存储对应的key，然后通过对应的key在hashmap找到对应的节点。插入元素的时候将节点插入链表头，这样保证每次新加入的数据在链表头，删除的时候从链表尾部删除。
\end{Mind}
\begin{longlisting}
	\caption{LRU缓存}
	\cppfile{third_party/coding/cxx/algorithm/datastruct/src/LRUCache.cc}
	\label{code:LRUCache}
\end{longlisting}
\begin{enumerate}
	\item 首先最近最少使用意味着如果我get了数据，数据就是被使用了，这时候数据节点应该插入到双链表头，以避免被删除。
	\item 删除节点的时候你需要找到节点，因为你需要节点key在cache里面删除它。所以删除节点的时候先从尾部找到节点然后删除。
	\item put的时候可能存在几种情况：
		\begin{itemize}
			\item key 已经在 cache 中存在，此时cache最多达到满容量的状态，所以我们直接更新节点的值。此时一定不会超过cache。
			\item key 不存在，而且此时容量已经满了，需要删除最后的元素，然后将新的节点插入链表头。
			\item key 不存在，而且此时容量没有满，则直接将节点插入链表头。
		\end{itemize}
\end{enumerate}
put的时候如果超过容量则删除最久没有使用的元素，如何为最久没有使用？插入的时候总是往链表头插入，所以链表尾部的就是最长没有使用的元素，删除双链表的尾部节点即可做到。
\subsection{\href{https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150}{实现 Trie (前缀树)}}
\begin{example}[实现Trie前缀树]
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：
\begin{itemize}
	\item Trie() 初始化前缀树对象。
	\item void insert(String word) 向前缀树中插入字符串 word 。
	\item boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
	\item boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
\end{itemize}
\begin{Textcode}
示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True
\end{Textcode}
\end{example}
\begin{Mind}{实现Trie前缀树}{}
前缀树搜索的时候，每个字符都有一些孩子节点。孩子节点记录下是否以其作为结尾。search意味着叶子节点以其结尾，startsWith意味着非叶子节点以其结尾。
\end{Mind}
例如插入apple，查找app开头。首先找到a节点，然后看a节点的孩子节点中是否存在p节点，接着从p开始找其孩子节点是否有p节点。此时p节点记录下了它以p结尾。所以返回True。\figref{fig:trie}简化了孩子节点的组成，原则上输入字符串是小写字母。我们需要根据字符索引到对应的节点。这里我们通过字符串在26个字母中的索引位置来确定存储了哪一个元素。当然也可以使用hash表通过字符索引对应的节点。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{trie}
	\caption{trie示意图}
	\label{fig:trie}
\end{figure}
\begin{longlisting}
	\caption{Trie树}
	\cudafile[firstline=5,lastline=66]{third_party/coding/cxx/algorithm/datastruct/include/trie.h}
	\label{code:trie}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150}{添加与搜索单词}}
\begin{example}[添加与搜索单词]
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：
\begin{itemize}
	\item WordDictionary() 初始化词典对象
	\item void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
	\item bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
\end{itemize}
\begin{bash}
输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

\end{bash} 
\end{example}
\begin{Mind}{添加与单词搜索}{}
	整体算法和Trie类似，不同在于通配符\textcolor{red}{.}的处理。搜索的时候一旦碰到\textcolor{red}{.}则在当前节点可用子节点找下一个字符。会存在多种情况：
	\begin{itemize}
		\item 存在一个子节点能找到目标则直接返回，不用查看其它可用节点。
		\item 所有可用节点都查询了，还是没有找到，此时返回为false。
	\end{itemize}
\end{Mind}
\begin{longlisting}
	\caption{添加与单词搜索实现}
	\cudafile[firstline=4,lastline=55]{third_party/coding/cxx/algorithm/datastruct/include/WordDictionary.h}
	\label{code:word_dictionary}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150}{O(1) 时间插入、删除和获取随机元素}}
\begin{example}[O(1) 时间插入、删除和获取随机元素]
O(1) 时间插入、删除和获取随机元素
实现RandomizedSet 类：
\begin{bash}
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
\end{bash}
\end{example}
\begin{Mind}{O(1) 时间插入、删除和获取随机元素}{}
这个问题的难点在于所有操作都需要O(1)，插入和删除可以通过HashMap实现O(0)，但是获取元素的时候不可以。元素如果使用数组存储则可以O(1)获取。所以数据结构上使用HashMap存储对应value的索引，然后通过索引在数据中获取对应元素。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{random_set}
	\caption{获取随机元素示意图}
	\label{fig:random_set}
\end{figure}
删除上还有一个难点，在列表中删除对应的值的时候会导致索引发生变化，因此需要反向更新hashmap中记录的值和索引对的关系。操作如\figref{fig:random_set_delete}。例如现在插入1,2,3,4之后hash表存放的结果为{1:0,2:1,3:2,4:3},数据表存放的为[1,2,3,4]。现在需要删除2，通过hash表找到索引idx=1。nums中数据1索引下的2应该被删除，我们直接使用数组中最后一个元素覆盖（原地交换也可以），此时最后一个元素和其相等，但是没关系我们会删除最后一个元素。此时我们相当于已经删除了2对应的索引，我们需要更新hash表中对应的索引。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{random_set_delete}
	\caption{删除操作示意图}
	\label{fig:random_set_delete}
\end{figure}
\begin{longlisting}
	\caption{O(1) 时间插入、删除和获取随机元素}
	\cppfile[firstline=2,lastline=29]{third_party/coding/cxx/algorithm/datastruct/src/RandomizedSet.cc}
	\label{code:randomed_set}
\end{longlisting}

\section{数学计算}
\subsection{求平方根}
\begin{Mind}{牛顿迭代法计算平方根}{}
	$f(x) = x^2-n$当函数表达式为0是求的的结果$x$即$\sqrt{n}$。假设给定一个$x_i$可以计算得到$f(x_i)=x_i^2-n$这个结果不一定为0（为0则$x_i$为所求解）。下一步计算该点切线方程和$x$轴的交点$x_{i+1}$同样计算此时的$f(x_{i+1})=x_{i+1}^2-n$，这时候$f(x_{i+1})$结果依然不一定为0,以新的$x_{i+1}$作为下一个计算点，反复迭代计算直到$x_{n}\approx x_{n-1}$或者是$f(n)=0$。当给定$x_i$时经过$x_{i}$的直线方程为：$y = f(x_i)+f'(x_i)(x-x_i)$切线方程为0求的下一个迭代点$x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}=x_i-\frac{x_i^2-n}{2x_i}=\frac{1}{2}(x_i+\frac{n}{x_i})$。
\end{Mind}
牛顿迭代法\figref{fig:sqrt}：
\begin{figure}[!htbp]
	\centering
	\begin{tikzpicture}[scale=0.7]
		\draw [help lines] (0,0) grid (8,9);
		\draw[<->,thick] (0,9) -- (0,0) -- (8,0);
		\draw[blue,ultra thick,domain=1:3.2] plot (\x,{\x*\x-2});
		\node[below right] at (3.3,7) {切点$x_i$};
		\draw[ultra thick,cyan,dashed] (0,7) node [left]{$f(x_i)$}--(3,7) node [left] {} --(3,0) node[above right] {$x_i$};
		\draw[ultra thick,cyan,dashed] (0,1.34) node [left]{$f(x_{i+1})$}--(1.83,1.34) node [left] {} --(1.83,0) node[below right] {$x_{i+1}$};
		\draw[red,ultra thick,domain=1.833:3] plot (\x,{6*\x-11});
		\draw[fill=red] (3,7) circle [radius=0.1];
		\draw[fill=red] (1.83,1.34) circle [radius=0.1];
		\draw[fill=green] (1.8,0) circle [radius=0.1];
		\node[below] at (5,8){$f(x)=x^2-2$};
		\node[below] at (8,0){$x$};
		\node[left] at (0,9){$f(x)$};
	\end{tikzpicture}
	\caption{求解平方根示意图}
	\label{fig:sqrt}
\end{figure}
\begin{longlisting}
	\caption{平方根}
	\cppfile[firstline=6,lastline=16]{third_party/coding/cxx/algorithm/common/src/sqrt.cc}
	\label{code:sqrt}
\end{longlisting}
\subsection{整数除法}
给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和取余运算。整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
\begin{Mind}{整数除法算法实现}{}
	如果被除数dividend大于除数divisor则商至少为1，于是加倍divisor，如果依然小于 dividend 则商跟着加倍，直到divisor>dividend为止。
\end{Mind}
例如：19/3。
\begin{itemize}
	\item 19>3，商至少为1，除数加倍为6。
	\item 19>6，商至少为2，除数加倍为12。
	\item 19>12，商至少为4，除数加倍为24。
	\item 24>19，商在4-8之间，如果除数是12则余数是7，余数7同样的方式计算包含两个3，则最后的结果为6。
\end{itemize}
这里面有几个坑：
\begin{itemize}
	\item 32位最小负数的绝对值比正数大1，如果被除数是最小值除数是-1直接求绝对值会导致溢出，这种情况直接返回最大整数。
	\item 负数只要不是最小值直接求绝对值不会溢出。
	\item 除数为0直接返回0。
	\item 除数加倍的过程可能会导致溢出，所以时机实现的时候是将int的数值转换为int64后运算的，自然不会有这个问题。
\end{itemize}
实现如\coderef{code:divide}。
\begin{longlisting}
	\caption{整数除法}
	\cppfile[firstline=3,lastline=39]{third_party/coding/cxx/algorithm/common/src/divide.cc}
	\label{code:divide}
\end{longlisting}

\subsection{阶乘后的0}
给定一个整数 n ，返回 n! 结果中尾随零的数量。
\begin{Mind}{阶乘后的0}{}
	阶乘的0由10产生，而10由$2\times5$产生。如果知道2、5中较小的那个值的个数即可知道0的个数。而因为是顺序递增，比较大的数5出现的次数一定不比2大。即问题变成了在1-n之间找到5的倍数的个数。
\end{Mind}
TODO重构代码实现
\subsection{圆圈中剩下的数字}
\begin{Textcode}
	0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3
\end{Textcode}
\begin{Mind}{圆圈中剩下的数字}{}
	上述问题可以描述为对于一个长度为n的数组组成的圆圈，每次向后删除第m个数之后最后剩余的元素。f(n,m) 用来描述删除之后剩下的数字，首先长度为n的删除m个数字m\%n后剩下n-1，假设f(n-1,m)=x，则f(n,m) = (m\%n+x)\%n=(m+x)\%m。f(n,m) = (m+f(n-1,m))\%m。其中f(1,m)=0（当只有一个元素的时候最后这个元素肯定是剩下的）。
\end{Mind}
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.6\textwidth]{lastRemaining}
	\end{center}
	\caption{圆圈中剩下的数字示意图}
	\label{fig:lastRemaining}
\end{figure}
递归实现\coderef{code:lastRemainingRec}：
\begin{longlisting}
	\cppfile[firstline=3,lastline=9]{third_party/coding/cxx/algorithm/common/src/lastRemaining.cc}
	\caption{圆圈中剩下的数字（递归实现）}
	\label{code:lastRemainingRec}
\end{longlisting}
迭代实现\coderef{code:lastRemaining}：

\begin{longlisting}
	\cppfile[firstline=11,lastline=17]{third_party/coding/cxx/algorithm/common/src/lastRemaining.cc}
	\caption{圆圈中剩下的数字（迭代实现）}
	\label{code:lastRemaining}
\end{longlisting}
\section{其它}
\subsection{整数转罗马数字}
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
\begin{table}[!htbp]
	\caption{罗马字符对应字符}
	\label{tab:intToRoman}
	\begin{center}
		\begin{tabular}{cc}
			\toprule
			字符 & 数值   \\
			\midrule  \\
			I  & 1    \\
			V  & 5    \\
			X  & 10   \\
			L  & 50   \\
			C  & 100  \\
			D  & 500  \\
			M  & 1000 \\
			\bottomrule
		\end{tabular}
	\end{center}
\end{table}
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
\begin{itemize}
	\item I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
	\item X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
	\item C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
	\item 给你一个整数，将其转为罗马数字。
\end{itemize}
\begin{Mind}{整数转罗马数字}{}
	扩充字符所代表的数值的字符串，贪心匹配，从大到小匹配数值，找到第一个小于num的结果，将对应的字符拼接。num减去对应的值，直到其小于当前匹配的数值后找到下一个。最后num=0则循环退出。如：\coderef{code:intToRoman}。
\end{Mind}

\begin{longlisting}
	\caption{整数转罗马数字}
	\cppfile[firstline=3,lastline=18]{third_party/coding/cxx/algorithm/common/src/intToRoman.cc}
	\label{code:intToRoman}
\end{longlisting}
\subsection{空间复杂度为1判断数字是不是回文数字}
\begin{example}[判断回文数字]
	判断回文数字，如12321是回文，123不是，回文数字关于数字中心对称。\\
\end{example}
\begin{Mind}{回文数}{}
用一个变量存储数字最高位，判断最高位，判断最低为和最高位是否相等，相等则删除最高位和最低为继续比较，循环结束的条件为这个数字小于0.
\end{Mind}
注意的是数字以12321为例首先获取首位和末尾相等，原则上下一步判断232是不是回文数字即可。但是对于1001这种数值，其中00不代表一个二位数值。所以这里的做法是每次尝试计算出高位和低位的值，x值本身不变。所以需要用来获取最高位的h\_base和获取最低位的l\_base。代码如\coderef{code:isPalindromeNum}。
\begin{longlisting}
	\caption{判断数字是否是回文数字}
	\cudafile[firstline=49,lastline=72]{third_party/coding/cxx/algorithm/common/src/array_common.cc}
	\label{code:isPalindromeNum}
\end{longlisting}

\subsection{下一个排列}
\begin{example}[下一个排列]
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。
\end{example}
\begin{Textcode}
	输入：nums = [1,2,3]
	输出：[1,3,2]
\end{Textcode}
\begin{Mind}{下一个排列}{}
	我们希望下一个数 比当前数大，这样才满足 “下一个排列” 的定义。因此只需要 将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
	我们还希望下一个数 增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
	\begin{itemize}
		\item 在 尽可能靠右的低位 进行交换，需要 从后向前 查找
		\item 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
		\item 将「大数」换到前面后，需要将「大数」后面的所有数 重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列
	\end{itemize}
\end{Mind}
\begin{itemize}
	\item 从后向前找到第一个相邻升序的元素索引（i，j），满足nums[i]<nums[j]，如果排列本身是逆序的（从大到小），则直接将数据反转。
	\item 从后向前找到第一个nums[k]>nums[j]的元素。
	\item 交换k和j对应位置的值（交换逆序导致值增加，我们还需要找到最小增加），此时[j,end]之间的数字必然是降序，也就是说j比后面的元素大，如果想获得更小的增幅，需要将j后面的元素排序。参考\figref{fig:nextPermutation}。
\end{itemize}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.95\textwidth]{nextPermutation}
	\end{center}
	\caption{下一个排列的算法示意图}
	\label{fig:nextPermutation}
\end{figure}

\begin{longlisting}
	\caption{下一个排列}
	\cppfile[firstline=3,lastline=21]{third_party/coding/cxx/algorithm/common/src/nextPermutation.cc}
	\label{code:nextPermutation}
\end{longlisting}
% \subsection{后缀表达式计算}
% \begin{example}[后缀表达式输出]
% 	扫描表达式，如果遇到“+”、“-”、、“*”、“/”将元素加入操作栈，如果是操作数则加入到后缀表达式，如果是"("也压入，但是当扫描的表达式出现")"的时候去要将操作数里面的内容全部出栈加入表达式。对于表达式(A+B*C)/D的后最表达式计算过程
% 	后缀表达式计算过程：将元素数据放入数据栈，操作放入操作栈，遇到操作就出栈，操作符是几元就出栈几个元素然后将元素计算后的结果放入数据栈继续扫描直到结束。
% 	\begin{figure}[H]
% 		\centering
% 		\includegraphics[width=\textwidth]{pos_express}
% 		\caption{后缀表达式计算}
% 	\end{figure}
% \end{example}
